package uestc.lj.basicPromotion.kmp;

/**
 * KMP算法求子串的问题
 *
 * @Author:Crazlee
 * @Date:2021/11/26
 */
public class Code01_KMP {
	/**
	 * kmp算法
	 *
	 * @param s 主串
	 * @param m 子串
	 * @return 返回子串在主串中的索引位置，不存在则返回-1
	 */
	public static int kmp(String s, String m) {
		if (s == null || m == null || m.length() < 1 || s.length() < m.length()) {
			return -1;
		}
		char[] str1 = s.toCharArray();
		char[] str2 = m.toCharArray();
		// 在str1中比对的位置
		int i1 = 0;
		// 在str2中比对的位置
		int i2 = 0;
		// 获取str2的next数组
		int[] next = getNextArray(str2);

		while (i1 < str1.length && i2 < str2.length) {
			if (str1[i1] == str2[i2]) {
				i1++;
				i2++;
			} else {
				if (next[i2] == -1) {
					i1++;
				} else {
					i2 = next[i2];
				}
			}
		}
		return i2 == str2.length ? i1 - i2 : -1;
	}

	private static int[] getNextArray(char[] str2) {
		if (str2.length == 1) {
			return new int[]{-1};
		}
		int[] next = new int[str2.length];
		next[0] = -1;
		next[1] = 0;
		int i = 2;
		//拿哪个位置的字符和i-1位置的字符相比
		int common = 0;
		while (i < str2.length) {
			if (str2[i - 1] == str2[common]) {
				next[i++] = ++common;
			} else {
				if (common > 0) {
					common = next[common];
				} else {
					next[i++] = 0;
				}
			}
		}
		return next;
	}

	public static void main(String[] args) {
		String str = "abcabcababaccc";
		String match = "ababa";
		System.out.println(kmp(str, match));

	}

}
